package LimitedTimeGame.Day_0228;

/**
 * @author zxc
 * @date 2023/02/28 07:52
 **/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目 ：合并相似物品
 * 题目详述 ：
 * 给你两个二维整数数组items1 和items2，表示两个物品集合。每个数组items有以下特质：
 * items[i] = [valuei, weighti] 其中valuei表示第i件物品的价值，weighti表示第 i件物品的 重量。
 * items中每件物品的价值都是 唯一的。
 * 请你返回一个二维数组ret，其中ret[i] = [valuei, weighti]，weighti是所有价值为valuei物品的重量之和。
 * 注意：ret应该按价值 升序排序后返回。
 *
 * 提示：
 *
 * 1 <= items1.length, items2.length <= 1000
 * items1[i].length == items2[i].length == 2
 * 1 <= valuei, weighti <= 1000
 * items1中每个 valuei都是 唯一的。
 * items2中每个 valuei都是 唯一的。
 *
 *
 */
public class MergeSimilarItems {
    /**
     * 思路 ：
     * ===》
     * （1）首先对于两个数组items1和items2进行排序;（从小到大进行排序）
     * （2）指针分别指向items1和items2数组中的第一个元素，逐步向后进行遍历;
     * （3）直至某个指针所指向的数组元素不存在时退出循环;
     * （4）最后，将为遍历完的数组中元素加入到result集合中去;
     *
     * @param items1
     * @param items2
     * @return
     */
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        // 对于两个数组进行排序;
        Arrays.sort(items1 , (p1 , p2) -> p1[0] - p2[0]);
        Arrays.sort(items2 , (p1 , p2) -> p1[0] - p2[0]);
        int len1 = items1.length;
        int len2 = items2.length;
        // 双指针
        int p1 = 0;
        int p2 = 0;
        List<List<Integer>> result = new ArrayList<>();
        while(p1 < len1 && p2 < len2){
            List<Integer> list = new ArrayList<>();
            if(items1[p1][0] < items2[p2][0]){
                list.add(items1[p1][0]);
                list.add(items1[p1][1]);
                p1++;
            }
            else if(items1[p1][0] > items2[p2][0]){
                list.add(items2[p2][0]);
                list.add(items2[p2][1]);
                p2++;
            }
            else {
                list.add(items1[p1][0]);
                list.add(items1[p1][1] + items2[p2][1]);
                p1++;
                p2++;
            }
            result.add(list);
        }
        while(p1 < len1){
            List<Integer> list = new ArrayList<>();
            list.add(items1[p1][0]);
            list.add(items1[p1][1]);
            p1++;
            result.add(list);
        }
        while (p2 < len2){
            List<Integer> list = new ArrayList<>();
            list.add(items2[p2][0]);
            list.add(items2[p2][1]);
            p2++;
            result.add(list);
        }
        return result;
    }
}
